package q1235_jobScheduling;

import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

public class Solution_2 {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        // treeMap 记录 endtime, profit, 然后dp
        int n = startTime.length;
        int[][] data = new int[n][3];
        for (int i = 0; i < n; ++i) {
            data[i][0] = startTime[i];
            data[i][1] = endTime[i];
            data[i][2] = profit[i];
        }
        Arrays.sort(data, (a, b)->{
            if (a[1] != b[1]) return a[1] - b[1];
            else if (a[0] != b[0]) return a[0] - b[0];
            return b[2] - a[2];
        });
        TreeMap<Integer, Integer> map = new TreeMap();
        map.put(0, 0); //
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            Map.Entry<Integer, Integer> entry = map.floorEntry(data[i][0]); // 找之前endTime小于等于当前startTime的最后一个节点
            int pro = Math.max(ans, entry.getValue() + data[i][2]); // ans记录的是到当前endTime以来
            if (pro > ans) ans = pro;
            map.put(data[i][1], pro);
        }
        return ans;
    }
}
